package com.company.algo.DichotomousSearch;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/valid-triangle-number/solution/you-xiao-san-jiao-xing-de-ge-shu-by-leet-t2td/
 */
public class valid_triangle_number {
    // 需要用排序来改善思路，使得a<=b<=c,只需要保证a+b>c即可
    public int triangleNumber1(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = 0;
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                //左边界查找(第一个小于nums[i]+nums[j]的下标k)
                int left = j+1, right = n, k = j;
                while(left < right){
                    int mid = left + (right - left)/2;
                    if(nums[mid]<nums[i]+nums[j]) {
                        k = mid;
                        left = mid + 1;
                    }else{
                        right = mid;
                    }
                }
                ans += k-j;
            }
        }
        return ans;
    }


    /**双指针优化
     我们将a=nums[i],b=nums[j]时，最大的满足nums[k]<nums[i]+nums[j]的下标k记为k_{i,j}，可以发现
     如果我们固定 i，那么随着 j 的递增，不等式右侧 nums[i]+nums[j] 也是递增的，因此 k_{i,j}
     也是递增的。
     */
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int k = i;
            for (int j = i+1; j < n; j++) {
                while (k+1 < n && nums[k+1]<nums[i]+nums[j]){
                    k++;
                }
                ans += Math.max(0,k-j);
            }
        }
        return  ans;
    }

    public static void main(String[] args) {
        valid_triangle_number Main = new valid_triangle_number();
        int[] nums = {2,2,4,4};
        System.out.println(Main.triangleNumber(nums));
    }
}
